package com.yangli.leecode.mashib.interview;

import java.util.Arrays;

/**
 * @Description
 * @Author liyang
 * @Date 2023/3/10 15:45
 */
public class FortyEight {
    public static void main(String[] args){
        System.out.println(FortyEight.count(new int[]{32, 2, 4, 8}, 3));

    }

    //正确答案
    public static int count2(int[] arr, int m){
        if (arr == null || arr.length == 0 || m < 1) {
            return 0;
        }
        if (arr.length == 1) {
            return 1;
        }
        Arrays.sort(arr);//==>复杂问题简单话，数据递增
        int pre = 1;
        for (int j = 1; j < arr.length; j++) {
            int num = find(arr, 0, j, arr[j] - m);//arr[0..j]有多少数是>=arr[j]-m，表示当前数字可以放置的位置：num,前面有n种方法，那后面则有num*n方法。
            pre = (num + 1) * pre;//还包括最后的一个位置
        }

        return pre;
    }

    public static int find(int[] arr, int i, int j, int k){
        int mid = 0;
        while (i <= j) {
            mid = (i + j) / 2;
            if (arr[mid] > k) {
                i = mid + 1;
            } else {
                j = mid - 1;
            }
        }
        return mid;
    }


    public static int count(int[] arr, int m){
        if (arr == null || arr.length == 0 || m < 1) {
            return 0;
        }
        if (arr.length == 1) {
            return 1;
        }
        boolean[] choose = new boolean[arr.length];
/*
        return process(arr, 0, -1, m, choose);
*/

        return process(arr, 0, m);

    }

    public static int process(int[] arr, int i, int pre, int m, boolean[] choose){
        if (i == arr.length) {
            return 1;
        }
        int ans = 0;
        for (int j = 0; j < arr.length; j++) {
            if (!choose[j] && ((pre - arr[j]) <= m)) {
                choose[j] = true;
                ans += process(arr, i++, arr[j], m, choose);//这个地方可以优化，数组排序，从大的开始选择，不满足后面的就不用递归了，
                choose[j] = false;
            }

        }
        return ans;
    }


    //优化的暴力递归
    public static int process(int[] arr, int i, int m){
        if (i == arr.length) {
            return 1;
        }
        int ans = 0;
        for (int j = i; j < arr.length; j++) {
            if (i == 0 || (arr[i - 1] - arr[j] <= m)) {
                swap(arr, i, j);
                ans += process(arr, i + 1, m);
                swap(arr, j, i);
            }
        }
        return ans;
    }

    public static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
